package primary.sort_and_merge;

/**
 * @Author Elephas
 * @Date 2022/1/8
 **/
public class Merge {

    /*
        解法一：
        边界情况：n=0 或 m=0
        一般情况，考虑使用m+n大小的辅助数组进行归并,时间复杂度O(n+m)空间复杂度O(n+m)
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
            return;
        } else if (n == 0) {
            return;
        }

        int[] temp = new int[m + n];
        int ptrNums1 = 0, ptrNums2 = 0, ptrTemp = 0;
        while (ptrNums1 < m && ptrNums2 < n) {
            if (nums1[ptrNums1] <= nums2[ptrNums2]) {
                temp[ptrTemp] = nums1[ptrNums1];
                ptrTemp++;
                ptrNums1++;
            } else {
                temp[ptrTemp] = nums2[ptrNums2];
                ptrTemp++;
                ptrNums2++;
            }
        }
        while (ptrNums1 < m) {
            temp[ptrTemp++] = nums1[ptrNums1++];
        }
        while (ptrNums2 < n) {
            temp[ptrTemp++] = nums2[ptrNums2++];
        }
        for (int i = 0; i < (m + n); i++) {
            nums1[i] = temp[i];
        }
    }

    /*
        解法二：一个位置一个坑，可以从后向前归并,原地归并，不使用额外空间
     */

    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        // 边界条件处理
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
            return;
        } else if (n == 0) {
            return;
        }

        // 一般情况
        int ptrNums1 = m - 1, ptrNums2 = n - 1, ptrResult = m + n - 1;
        while (ptrNums1 >= 0 && ptrNums2 >= 0) {
            if (nums1[ptrNums1] > nums2[ptrNums2]) {
                nums1[ptrResult--] = nums1[ptrNums1--];
            } else {
                nums1[ptrResult--] = nums2[ptrNums2--];
            }
        }
        while (ptrNums2 >= 0) {
            nums1[ptrResult--] = nums2[ptrNums2--];
        }

        return;
    }
}
